package LeetCode刷题.暑假刷的算法;

/**
 * @program: Java_Study
 * @author: Xiaofan
 * @createTime: 2021-08-14 15:18
 * @description: Functions of this class is 复制一棵二叉树
 **/
public class 复制一棵二叉树 {
    private static class TNode{
        TNode left,right;
        int val;
    }
    public static void main(String args[]){
        TNode oldTree=createTree();
        System.out.print("旧的树为：");
        preOrder(oldTree);
        System.out.println();
        TNode newTree=copyTree(oldTree);
        System.out.print("复制后的新树为：");
        preOrder(newTree);
        System.out.println();
    }

    private static TNode copyTree(TNode oldTree) {
        TNode newTree=null;
        if(oldTree!=null){
            //先建立一个新的树节点
            newTree=new TNode();
            newTree.val=oldTree.val;
            newTree.left=copyTree(oldTree.left);//复制左子树
            newTree.right=copyTree(oldTree.right);//赋值右子树
        }
        return newTree;
    }

    private static TNode createTree() {
        TNode root = new TNode();

        TNode node1 = new TNode();
        TNode node2 = new TNode();
        TNode node3 = new TNode();
        TNode node4 = new TNode();
        /*
                6
             3    -7
          -1   9
         */
        root.val = 6;
        node1.val = 3;
        node2.val = -7;
        node3.val = -1;
        node4.val = 9;
        root.left = node1;
        root.right = node2;
        node1.left = node3;
        node1.right = node4;
        node2.left = node2.right = node3.left = node3.right = node4.left = node4.right = null;
        return root;
    }
    public static void preOrder(TNode T){
        if(T!=null){
            System.out.print(T.val+" ");
            preOrder(T.left);
            preOrder(T.right);
        }
    }
}